关注社区微信公众号: PMvideo
作者: 2017-11-26 收录到我的专题
前段时间有幸跟 NOVA 的作者 Jian Xu 博士深入交流了一番,受益颇多,决定趁热打铁,好好研究一下 NOVA,一方面可以知道在 Linux 下面如何开发一个文件系统,而另一方面,则是想了解下当前硬件的发展水平,以及为了更好的发回硬件性能,我们需要做什么,算是对未来做一些技术调研和储备工作。
NOVA 是一个支持混合 Volatile/Non-volatile main memories 的文件系统,volatile main memory 其实 我们很容易理解,就是我们通常说的 DRAM。而 Non-volatile main memory (NVM) 则可以认为是跟 DRAM 有一样的性能(可能还是稍微比 DRAM 慢一点),但能进行数据持久化的技术,譬如我司现在就有十块基于 NVM 技术的 3D XPoint 盘,如果有同学对这块感兴趣,想尝试下为最近硬件设计程序,欢迎联系我。
NVM 预计很快就会跟 DRAM 一样,出现在处理器内存总线上面,所以融合 DRAM 和 NVMM 的特性,设计出一套更好的存储系统,我认为是有必要的。现阶段,传统的文件系统,譬如 XFS,ext4 并不能和好的工作于这种混存架构上面,所以徐博士他们就设计了一个 Non-Volatile memory Accelerated (NOVA) 的文件系统。
这里,再说一点小插曲,我开始以为 NVMM 和 NVMe 是一样的东西,于是问了徐博士这个问题,结果他告诉我两个是不一样的,真的是差之毫厘谬以千里,看来我在硬件上面的知识积累不足,后面需要多跟徐博士他们这些牛人请教。
在开始讨论 NOVA 之前,我们可以先说说 NVMM,NVMM 这种新的硬件体系给文件系统的设计带来了新的挑战,主要有几个方面:
clflush
会极大的降低性能,而 mfence
并不能保证写回到 NVMM 的顺序。幸运的是,Intel 已经开发了新的指令集 clfushopt
, clwb
,PCOMMIT
,而 NOVA 就是基于这些新的指令集的。(跟徐博士聊天顺带问了下 AMD 是否也有了类似的指令集,他回答『不确定,不过应该是有了』)。通常文件系统实现原子性有几种方式:
现阶段,基于 NVMM 的文件系统已经有不少了,譬如 Ext4-DAX(感觉原生的 Ext4 应该是不适用与 NVMM 的),它采用的是 Journaling 的方式,但只保证 metadata 的更新原子性,并没有保证数据的。
而 NOVA 是一个使用 log-structuring 的文件系统,但为了更好的利用 NVMM,NOVA 并没有直接使用传统的 log-structuring 的方式,而且做了改进。徐博士他们在做 NOVA 的时候,发现几个现象:
观察到以上现象之后,NOVA 就做了如下设计:
上图是 NOVA 的整体架构,NOVA 将 NVMM 分成了四块,superblock 和 recovery inode,inode tables, journals,最后就是 log / data pages。Superblock 包含了全局的文件系统信息,而 recovery inode 则存放了用于下一次启动加速 NOVA remount 的恢复信息,inode tables 则包含 inodes,而 journals 则是为目录操作提供了原子支持,剩下的就是实际的 log 和 data 的 pages。
NOVA 为每个 CPU 设置了自己的 inode table,journal,page list,这样就能避免不同的 CPU 之间的 lock 问题。这个优化其实在 RocksDB 的 statistics 上面也有体现,它也使用了 per-CPU 模型,每个 CPU 负责自己的统计信息。
NOVA 首先会 为每一个 inode table 初始化一个 2 MB 的 inodes array,每一个 inode 都是 128 byte 字节,所以给定一个 inode number,NOVA 会很容易就定位到对应的 inode。
对于新增的 inode,NOVA 会使用 round-robin 算法,依次添加到各个 inode table 上面,保证整个 inodes 的均匀分布。如果一个 inode table 满了,NOVA 会再分配一个 2 MB 的 sub-table,并用链表串联起来。为了减少 inode table 的大小,每个 inode 上面有一个 bit 来表示是否 invalid,NOVA 就能重用这些 inode 给新的文件或者目录了。
一个 inode 包含指向 log 的 head 和 tail 指针,log 是一个由 4 KB page 串联的链表,tail 一直指向的是最后一个提交的 log entry,当系统第一次访问 NOVA 的时候,NOVA 会通过遍历 head 到 tail 的所有 log 去重建 DRAM 里面的数据结构。
NOVA 的 journal 是一个 4 KB 的环形 buffer,使用一对 <enqueue, dequeue>
指针来操作这个 buffer。Journal 主要是为了保证操作多个 inode 的原子性,首先 NOVA 会将更新追加到 inode 的各自 log 上面,然后开启一个事务,将涉及到的 log tail 写入当前 CPU 的 journal enqueue,并且更新 enqueue 指针,当 各个 inode 完成了自己的更新,NOVA 就更新 dequeue 指针到 enqueue,完成事务的提交。
NOVA 将 NVMM 给每个 CPU 分了一个 pool,然后将空闲的 page list 保存在了 DRAM 里面。如果当前 CPU pool 里面没有可用的 page,就从最大的 pool 里面拿。NOVA 使用 red-black tree 按照 address 来存放空闲的 pages,正常关机下面,NOVA 会将分配好的 page 状态保存到 recovery inode 的 log 里面,但如果是非正常关机,则会遍历所有 inode 的 log 并重建。
最开始,一个 inode 的 log 只有一个 page,当需要更多 page 的时候,NOVA 直接使用 x 2 的方式,但如果 log 的长度超过了一定阈值,就每次只新分配固定数量的 pages 了。
前面简单的介绍了一些 NOVA 的架构以及基本的数据结构,下面介绍下一些常用功能的大概实现。
NOVA 的目录包括两块,一个是保存到 NVMM 里面的 inode log,另一个则是放到 DRAM 里面的 radix tree。目录的 log 包括 directory entires (也就是通常的 dentry) 和 inode update entires。Dentry 包括目录名,子目录,子文件,inode 个数,还有 timestamp 这些信息。对于改目录下面的文件操作,譬如 create,delete,rename 这些,NOVA 都会在 log 里面追加一个 dentry。 对于 delete 操作来说,NOVA 会将 dentry 的 inode number 设置为 0,用以跟 create 区分。
为了加快 dentry 的查询速度,NOVA 在 DRAM 里面维护了一个 radix tree,key 就是 dentry 的名字,而 tree 的子节点则指向 log 中对应的 dentry。
上面是一个 create 的例子,我们要创建一个 zoo 的目录,会有如下几个操作:
NOVA 的文件 log 包含两种,一个是 inode update entries,另一个 write entries,write entry 里面会描述 write operation 以及指向实际的 data page。如果一次写入太大,NOVA 会使用多个 write entries,并将它们全部追加到 log 后面,然后最后更新 log tail。
上面是一个文件写入例子,上面的 <0, 1>
这种的表示 <filepageoff, num pages>
,也就是 page 的 offset 和有多少个 page。譬如 <0, 1>
就表示这个 page 的 offset 是 0, 有一个 page,也就是 4 KB。当我们要进行一次 <2, 2>
写入(也就是在 offset 为 2 的地方重新写入 2 pages),流程如下:
<2, 2>
追加到 inode log 上面上面需要注意,虽然我们更新 log tail 是原子的,但并没有保证原子更新 log tail 和 radix tree,这里跟徐博士讨论的时候他说到,使用了一个 read-write lock,其实他觉得并不高效,后面考虑优化。
我们可以使用 DAX-mmap 技术将 NVMM 的数据直接映射到用户空间,采用这种方式,我们能直接绕过文件系统的 page cache,虽然能降低开销,但对于程序员来说还是有很大的挑战,上面说了,NVMM 只有 64 位的原子操作支持,而且一些 fence 和 flush 指令还需要依赖处理器,所以先基于这些初级的机制构造健壮的 non-volatile 的数据结构,其实是非常困难的。
为了解决这个问题,NOVA 使用了一种 atomic-mmap 的机制,它其实是使用了一个 replica pages,然后将实际修改的数据放到了 replica pages 上面,当用户调用了 msync 操作,NOVA 就会将相关的修改当做一次 write 操作处理,它会使用 movntq 指令将 replica pages 的数据拷贝到 data pages,然后在原子性的提交。
虽然采用这种方式能保证数据强一致,但并没有 DAX-mmap 高效。而对于通常 DRAM 的 mmap,NOVA 现在并不支持,未来可能有计划。
NOVA 将文件的 metadata 和实际 data 不同存放,这样对于 GC 来说其实是很高效的。对于 data 来说,只要 write 操作产生了 stale data pages(就譬如我们前面说的那个例子),NOVA 就直接对 data pages 进行回收。
但回收 inode logs 就比较复杂了。我们需要确认一个 log entry 是 dead 的,首先这个 entry 不能是 log 的最后一个 entry,并且需要满足以下任意一个条件,就可以认为是 dead 了:
NOVA 使用两种 GC 方式,Fast GC 和 Thorough GC。
当 NOVA 发现一个 log page 里面所有的 entries 都是 dead,那么就可以直接回收这个 page,这个仅仅需要更新 page 的指针就可以了。譬如上面流程 a 就是 Fast GC 的例子,2 这个 page 只有 dead entries 了,我们只需要将 page 1 的 next pointer 指针指向 page 3 就可以了。
如果一个 log page 里面 live entries 的数量小于一半了,NOVA 就会开始进行 Thorough GC,就是将 live entries 拷贝到另一个新的 log 上面,指向新的 log,并且回收旧的 log。上面的流程 b 就是 Through GC 的例子,NOVA 将 page 1 和 3 的 entries 拷贝到 page 5 上面,然后链接 page 5 和 page 4,并且回收 page 1 和 3。这里 NOVA 并没有处理 page 4 的 live entries,这样就用原子更新 log head,从而避免同时更新 log head 和 tail,这个没法保证原子性。
当系统关闭并重新启动之后,NOVA 就会重现去 mount,它使用了一种延迟重建的机制,也就是只有第一次访问的时候才会去重建 radix tree 这些。对于正常关机来说,因为 NOVA 会将所有的 page 分配状态都保存到 recovery inode log 里面,所以 remount 的时候只需要从 recovery inode log 恢复就可以了。
但对于异常关机(譬如掉电)来说,NOVA 就必须重建 page 分配状态,NOVA 就需要遍历所有的 inode logs 了。但这个速度也是很快的,因为首先能每个 CPU 并发去恢复,另外,因为 log 里面不包含 data,所以 log 比较短,恢复速度自然就很快。在恢复的时候,NOVA 需要处理:
NOVA 的源码在 GitHub ,大家如果感兴趣,可以去学习一下,毕竟对于如何在新硬件体系上面做一个文件系统这种事情,还是非常酷的。这篇文章也算是我对 NOVA 的一些探究,里面如果有不对的地方,如果徐博士看到了,麻烦指正出来。
对于新硬件体系的研究,以及如何基于这些硬件体系更好的设计数据库的存储引擎,是我们未来重点会跟进的一个方向,欢迎各位对这方面感兴趣的同学加入我们 PingCAP,你可以直接给我发邮件 tl@pingcap.com。毕竟从头开始打造一个未来的存储引擎,我觉得是一件非常有意思,有挑战的事情。
笔记社区是一个面向中高端IT开发者、程序员的知识共享社区,通过网络抓取与文章分类总结,由专家为用户提供高质量的专题文章系列。 邀请您成为社区专家 >>
原文链接:http://www.jianshu.com/p/b403a10edfed
声明:所有文章资源均从网络抓取,如果侵犯到您的著作权,请联系删除文章。联系方式请关注微信公众号PMvideo【锤子视频-程序员喜欢的短视频】,笔记社区开发者交流群 628286713。
December
今日签到1人
0条评论或问题